import java.io.BufferedReader;
import java.io.DataInputStream;
import java.io.FileInputStream;
import java.io.FileWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Collection;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Set;

public class Regex {
	String pattern;
	DeterministicFiniteAutomaton dfa;
	Set<Character> alphabet;
    boolean debug;

    /**
     * Constructs a regex object based on a single pattern.
     * @param pattern the immutable pattern that this regex matches
     */
	public Regex(String pattern) {
		NonFA nfa = new NonFA();
		// make the DFA, minimize it, and store it
		nfa.buildFromRegex(parseFinal(pattern));
		DeterministicFiniteAutomaton dfa = nfa.toDFA().minimize();
		this.dfa = dfa;
		this.alphabet = dfa.getAlphabet();
		this.pattern = pattern;
        this.debug = false;
	}

	/**
	 * When set to true, turns on debug output
	 * @param b debug on/off
	 */
    public void setDebug(boolean b){
        debug = b;
    }
	
    /**
     * Searches a file for instances of this regex's pattern
     * @param filename file to search
     * @return list of matches with metadata
     */
	public ArrayList<StringMatchObject> find(String filename) {
		Map<String,StringMatchObject> matches = new HashMap<String,StringMatchObject>();
		
		FileInputStream fs;
		try {
			// open the file
			fs = new FileInputStream(filename);
			DataInputStream ds = new DataInputStream(fs);
			BufferedReader br = new BufferedReader(new InputStreamReader(ds));
			String dataIn, matchedString;
			int prevCharSum = 0;
			// handle the file line by line
			while ((dataIn = br.readLine()) != null) {

                if (debug) System.out.println("Regex's File Data:" + dataIn);

				int marker = -1;
				// loop until we're out of characters in this line
				while (marker < dataIn.length()) {
					// find the start of the next non-whitespace token
					while (++marker < dataIn.length() && Character.isWhitespace(dataIn.charAt(marker)));
					// find the end of the next non-whitespace token
					int end = marker;
					while (++end < dataIn.length() && !Character.isWhitespace(dataIn.charAt(end)));
					// if we've run over, stop the loop
					if (marker > dataIn.length() || end > dataIn.length()) break;
					// get the token that we just found
					String s = dataIn.substring(marker, end);
					// try to match the token
					if ((matchedString = match(s)) != null) {
						if (!matches.containsKey(matchedString)) {
							// if we haven't seen this string yet, make a new
							// match object for it and set it up
							StringMatchObject o = new StringMatchObject();
							o.setLiteral(matchedString);
							matches.put(matchedString, o);
						}
						// note that we found an instance of this string
						matches.get(matchedString).addLocation(filename, prevCharSum + marker);
					}
					// next time, start looking at the end of the token we just matched
					marker = end;
				}
				// keep track of how many chars we've been through (for metadata)
				prevCharSum += dataIn.length();
			}
	
			// close file stream
			br.close();
			ds.close();
			fs.close();
		} catch (IOException e) {
			e.printStackTrace();
			System.err.println("Problem with filo i/o");
			System.exit(1);
		}
		// put the output into a nice arraylist
		ArrayList<StringMatchObject> out = new ArrayList<StringMatchObject>();
		for (StringMatchObject o : matches.values()) out.add(o);
		return out;
	}
	
	private String match(String token) {
		// start with the dfa in a clean state
		dfa.resetToStartState();
		String inputSeenSoFar = "";
		String longestMatch = "";
		for (Character c : token.toCharArray()) {
			if (!alphabet.contains(c)) {
				// if this char isn't in the alphabet, it *can't* be a match
				break;
			}
			// remember how far we are into the token
			inputSeenSoFar += c;
			// execute a dfa transition
			dfa.doTransition(c);
			// if the dfa accepts, remember the token at this point in case it
			// doesn't match the rest of the token. this gets longest match.
			if (dfa.isInAcceptingState()) longestMatch = inputSeenSoFar;
		}
		// only return longest match if there was a match, otherwise null is
		// much more descriptive
		if (longestMatch.length() > 0)
			return longestMatch;
		else
			return null;
	}
	
	/**
	 * Go through a file, replacing instances of this regex's pattern with some
	 * string.
	 * @param readFile
	 * @param writeFile
	 * @param replaceWith
	 */
	public void replace(String readFile, String writeFile, String replaceWith) {
		ArrayList<String> input = new ArrayList<String>();
		BufferedReader br;
		try {
			br = new BufferedReader(new InputStreamReader(new DataInputStream(new FileInputStream(readFile))));
		
		String line;
		// read the input file to the arraylist
		while ((line = br.readLine()) != null)
			input.add(line);
		br.close();
		
		// do the replacement
		List<String> body = replaceString(input, replaceWith);
		
		// write out the array to a file
		PrintWriter out = new PrintWriter(new FileWriter(writeFile));
		for (String s : body) out.println(s);
		// close the file
		out.close();
		} catch (IOException e) {
			e.printStackTrace();
			System.err.println("Problem with filo i/o");
			System.exit(1);
		}
	}
	
	/**
	 * This function does the real work of replacement. It doesn't have to
	 * worry about file i/o.
	 * @param input
	 * @param replaceWith
	 * @return
	 */
	private List<String> replaceString(List<String> input, String replaceWith) {
		// do the replace
		String matchedString;
		for (int i=0; i<input.size(); i++) {
			String dataIn = input.get(i);
			int marker = -1;
			while (marker < dataIn.length()) {
				// find the start of the next non-whitespace token
				while (++marker < dataIn.length() && Character.isWhitespace(dataIn.charAt(marker)));
				// find the end of the next non-whitespace token
				int end = marker;
				while (++end < dataIn.length() && !Character.isWhitespace(dataIn.charAt(end)));
				// if we're past the end, stop the loop
				if (marker > dataIn.length() || end > dataIn.length()) break;
				String s = dataIn.substring(marker, end);
				// do stuff it this token matches
				if ((matchedString = match(s)) != null) {
					// grab what's before and after the match
					String pre = dataIn.substring(0, marker);
					String post = dataIn.substring(marker+matchedString.length(), dataIn.length());
					// perform the change and reload dataIn
					input.set(i, pre + replaceWith + post);
					dataIn = input.get(i);
					// adjust the marker for the replacement
					marker = end + (replaceWith.length() - matchedString.length());
				} else
					// if there was no replacement, change the marker normally
					marker = end;
			}
		}
		
		return input;
	}
	
	/**
	 * Like replace(), but does it recursively
	 * @param readFile
	 * @param writeFile
	 * @param replaceWith
	 */
	public void recursiveReplace(String readFile, String writeFile, String replaceWith) {
		if (match(replaceWith) != null) {
			// stop if this operation would replace strings with something
			// that the pattern would match (infinite loop)
			System.err.println("recursivereplace would recurse infinitely");
			System.err.println("pattern \"" + pattern + "\" matches string \"" + replaceWith + "\"");
			System.exit(1);
		}
		try {
			// open the file
			ArrayList<String> input = new ArrayList<String>();
			BufferedReader br = new BufferedReader(new InputStreamReader(new DataInputStream(new FileInputStream(readFile))));
			
			String line;
			// read the input file to the arraylist
			while ((line = br.readLine()) != null)
				input.add(line);
			br.close();
			
			List<String> body = input;
			List<String> oldBody;
			// replace until there's no change between two consecutive
			// iterations (no more recursion to be done)
			do {
				// do a deep copy, body -> oldBody
				oldBody = new ArrayList<String>();
				for (String s : body) oldBody.add(s);
				// perform the replacement
				body = replaceString(input, replaceWith);
			} while (!equalsStringLists(body, oldBody));
	
			// write out the array to file
			PrintWriter out = new PrintWriter(new FileWriter(writeFile));
			for (String s : body) out.println(s);
			out.close();
		} catch (IOException e) {
			e.printStackTrace();
			System.err.println("Problem with filo i/o");
			System.exit(1);
		}
	}
	
	/**
	 * Convenience function that compares two lists of strings for recursivereplace()
	 * @param a
	 * @param b
	 * @return whether a and b are equivalent
	 */
	private boolean equalsStringLists(List<String> a, List<String> b) {
		if (a.size() != b.size()) return false;
		for (int i=0; i<a.size(); i++) {
			if (!a.get(i).equals(b.get(i))) return false;
		}
		return true;
	}
	
	public static void main(String[] args) throws IOException {
		Regex re = new Regex("f[a-z]*");
//		List<StringMatchObject> matches = re.find("minire_test_script.txt");
//		for (StringMatchObject o : matches) {
//			System.out.println(o.getLiteral());
//		}
		re.recursiveReplace("minire_test_script.txt", "hi3.txt", "f1nd");
	}

	//copying over a dirty hack and hoping it works
	public String parseFinal(String s) {
		String f = new String();
		char ch, nch; 
		boolean flag = false;

		for(int i = 0; i < s.length(); ) {

			if ( s.charAt(i) == '\\' ) {
				f = f.concat( s.substring(i, i+2) );
				i+=2;
			}
			else if ( (i+1) < s.length() && s.charAt(i) == '[' && s.charAt(i+1) != '^' ) {
				f = f.concat ( "(" + s.substring(i, i+4) );
				i+=4;
			
				while (((i) < s.length()) && (s.charAt(i) != ']'))  {
					flag = true;
					f = f.concat( "]|[" + s.substring(i, i+3) );
					i += 3;
				}
				f = f.concat( "])" );
				i++;
			
			}
			else if ( (i+2) < s.length() && s.substring(i, i+2).equals("[^") ) {
				//handle the not case.
				//Example [^0]IN[0-9]
			
				if ( s.charAt(i+3) == '-' ) { // complex case [^a-b]in[a-zA-Z0-9]
	
					char rlb = s.charAt(i+2);
					char rub = s.charAt(i+4);

					List<Character> accepts = new ArrayList<Character>();

					i += 9;
					while( s.charAt(i) != ']' ) { // [^A-C]IN[A-La-z]

						for( char _ch = s.charAt(i); _ch <= s.charAt(i+2); _ch++) if( _ch < rlb || _ch > rub) accepts.add( ((Character)_ch) );

						i+=3;
					}

					f = f.concat( "(" );
					for( int k = 0; k < accepts.size() -1; k++ ) f=f.concat( String.valueOf(accepts.get(k)) + "|" );
					f = f.concat( accepts.get(accepts.size()-1) + ")" );

					i += 1;
					
				}
				else { //Simple case
					f = f.concat( "(" );
					nch = s.charAt(i+2);
					for( ch = s.charAt(i+7); ch < s.charAt(i+9); ch++ ) if ( ch != nch ) f = f.concat( String.valueOf(ch) + "|" );
					ch = s.charAt(i+9);
					if ( ch != nch ) f = f.concat( String.valueOf(ch) + ")" );
					i+=11;
				}

				
			}
			else if ( s.charAt(i) == '+' ) {
				f = f.concat( String.valueOf(s.charAt(i-1)) + "*" );
				i++;
			}
			else {
				f = f.concat( ((Character)s.charAt(i)).toString() );
				i++;
			}
		}

		return f;
	}


}
